There are a number of conventional algorithms for generating message digests in response to messages. Examples include the SHA-1, MD4, and MD5 algorithms. Such algorithms have been implemented in hardware as well as in software. The common characteristic of these algorithms is that they can take a very large message and condense it into a much smaller “message digest” (sometimes referred to as a “digest”). The digest is very sensitive to even the smallest change in the original message. Therefore any change to or substitution of the message is likely (with a very high probability) to be discovered by comparing digests of the original message and the changed or substituted message. Another characteristic of a message digest is that the digest leaks very little information about the original message.
Message digests have well known uses in the cryptography world, especially in digital signature algorithms and the like. The inventor has recognized that the very characteristics that make the message digests good for these conventional purposes would also make them suitable for testing the internals of an integrated circuit. During testing of a chip in accordance with some embodiments of the invention, the “message” to be digested is the internal state of the chip (or some aspect of such internal state). The internal state can be quite complex and can vary over time in complicated ways. Moreover, very little of it may be observable outside the chip under ordinary circumstances.
Conventional solutions to the problem of how to test a chip typically make use of “scan chains,” which seek to capture much of the internal state and make it visible outside the chip. In typical test using a scan chain, register values are serially shifted into the chip, the chip is operated for some period of time, and a resulting set of register values is serially extracted from the chip. However, scan chains are not an ideal solution for a number of reasons, including the following:
scan chains add complexity to the chip and slow down timing paths. This increases cost and reduces performance;
scan chains cannot be used during normal operation. They are only available in special test modes;
scan chains typically can only capture the state of the chip at one particular moment in time. Capturing multiple states can be done only slowly (one at a time), and at risk of altering the internal state;
scan chains make a chip's internal state visible. While this helps to test the device, it significantly reduces the security of the information the chip contains (such as cryptographic keys);
scan chains can be used to alter the internal state of a device. White this is desirable in some cases, it can be a significant problem in others (such as security applications). A scan operation can alter the device's internal state in a number of ways. For example, a memory array that is not part of the scan chain could be corrupted or erased as unusual states cycle through its control registers; and
scan chains are not suitable for all kinds of logic, such as large memory arrays.
Before the present invention, the testability of integrated circuit implementations of cryptographic devices that use unique key sets had been limited due to the need to keep confidential some (or some aspects) of the devices' internal states to avoid releasing cryptographically sensitive information. However, in accordance with the invention, such devices can be tested using message digests without releasing cryptographically sensitive information.
Message digests have been generated by chips for purposes other than testing the chips. For example, repeater chips that implement the cryptographic protocol known as the “High-bandwidth Digital Content Protection” (“HDCP”) protocol have generated digests (indicative of key selection vector lists) during authentication exchanges. However, these digests have been generated and used for security purposes; not for testing the internal state of a chip in which a digest has been generated.